package Hot100.Medium.BinarySearch;

/**
 * 搜索二维矩阵，矩阵每一行以及每一列都是递增的。
 * 可以考虑对每一行进行二分，直到找到结果为之。
 */
public class LC240 {
    public static void main(String[] args) {
        int[][] matrix = {{1,4,7,11,15},{2,5,8,12,19}};
        int target = 5;
        LC240 solution = new LC240();
        System.out.println(solution.searchMatrix(matrix,target));
    }

    public boolean searchMatrix(int[][] matrix, int target){
        int row = matrix.length;
        int line = matrix[0].length;
        for(int i = 0; i < row; i++){
            if(binarySearch(matrix[i], target)){
                return true;
            }
        }
        return false;
    }

    public boolean binarySearch(int[] nums, int target){
        int left = -1;
        int right = nums.length;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target){
                right = mid;
            } else {
                left = mid;
            }
        }
        return right < nums.length && nums[right] == target;
    }
}
